//
// Created by Administrator on 2022/1/2.
//

#ifndef CPP_LEARNING_BST_HPP
#define CPP_LEARNING_BST_HPP
#include "bin_tree.hpp"
#include "utils.h"
template <typename T>
class BST : public BinTree<T>{
protected:

    BinNodePosi(T) _hot;   // 命中节点的父亲
    BinNodePosi(T) connect34(BinNodePosi(T), BinNodePosi(T), BinNodePosi(T),
                             BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), BinNodePosi(T));

    BinNodePosi(T) rotateAt(BinNodePosi(T) x);

    BinNodePosi(T) removeAt(BinNodePosi(T)node ,BinNodePosi(T) & hot);

public:
    virtual BinNodePosi(T)  search(const T&e);   // 查找
    virtual BinNodePosi(T) insert(const T& e);    // 插入
    virtual bool remove(const T&e);           // 删除

};
template <typename T>
BinNodePosi(T) BST<T>::connect34(BinNodePosi(T)nodel, BinNodePosi(T)node, BinNodePosi(T)noder,
                         BinNodePosi(T)nodell, BinNodePosi(T)nodelr, BinNodePosi(T)noderl, BinNodePosi(T)noderr){

    node->lc = nodel;
    nodel->parent = node;
    node->rc = noder;
    noder->parent = node;

    if(nodel) nodel->lc = nodell;
    if(nodell) nodell->parent = nodel;
    if(nodel) nodel->rc = nodelr;
    if(nodelr) nodelr->parent = nodel;

    if(noder) noder->lc = noderl;
    if(noderl) noderl->parent = noder;
    if(noder)  noder->rc = noderr;
    if(noderr) noderr->parent = noder;

    this->updateHeight(nodel);
    this->updateHeight(noder);
    this->updateHeight(node);
    return node;
}


/**
 *         g
 *     p
 * v
 *
 */
template <typename T>
BinNodePosi(T) BST<T>::rotateAt(BinNode<T> *v) {
    BinNodePosi(T) p = v->parent;
    BinNodePosi(T) g = p->parent;

    if(IsLChild(*p)){
        if(IsLChild(*v)){
            /**
              *         g
             *     p
             * v
             */
             p->parent = g->parent;
            return connect34(v, p, g, v->lc, v->rc, p->rc, g->rc);
        }else{
            /**
              *          g
             *   p
             *        v
             */
             v->parent = g->parent;
            return connect34(p,v,g,p->lc,v->lc,v->rc,g->rc);
        }
    }else{
        if(IsRChild(*v)){
            /**
              *         g
             *              p
             *                   v
             */
            p->parent = g->parent;
            return connect34(g, p, v, g->lc, p->lc, v->lc, v->rc);
        }else{
            /**
              *          g
             *                     p
             *                v
             */
            v->parent = g->parent;
            return connect34(g,v,p,g->lc,v->lc,v->rc,p->rc);
        }
    }
}

template <typename T>
BinNodePosi(T)  BST<T>::search(const T&e){
    BinNodePosi(T) node = this->_root;
    _hot = NULL;
    while (node){
        if(node->data == e){
            _hot = node->parent;
            return node;
        }
        else if(e <  node->data)
        {
            _hot = node;
            node = node ->lc;
        }
        else if(e >  node->data)
        {
            _hot = node;
            node = node ->rc;
        }
    }
    return NULL;
}

/**
 * 返回插入的节点的指正
 * @tparam T
 * @param e
 * @return
 */
template <typename T>
BinNodePosi(T) BST<T>::insert(const T &e) {
    _hot = NULL;
    BinNodePosi(T) node = this->_root;
    while (node){

        if(e <  node -> data )
        {
            _hot = node;
            node = node -> lc;
        }
        else if(e >  node -> data )
        {
            _hot = node;
            node = node ->rc;
        }

    }
    // 要调用bintree的api
    if(_hot ==NULL){
        node = this->insertAsRoot(e);
    }
    else if(e <  (_hot -> data)){
        node = this->insertAsLC(_hot,e);
    }
    else if(e >  (_hot -> data)){
        node = this->insertAsRC(_hot,e);
    }
    return node;
}


/**
 * _hot 是一个传出参数
    记录这实际删除的那个节点的父节点
    返回实际被删除者的接替者
 */
template <typename T>
BinNodePosi(T) BST<T>::removeAt(BinNodePosi(T)node ,BinNodePosi(T) & hot){
    // 情况一 叶子节点, 要删除的节点就是这个节点
    BinNodePosi(T) deleteNodeSucc = NULL;
    if(IsLeaf(*node)){
        hot = node->parent;
        FromParentTo(*node) = NULL;
        deleteNodeSucc = node->lc;
        delete node;
        return deleteNodeSucc;
    }

    //单分支    要删除的节点就是这个节点
    if(HasLChild(*node) && !HasRChild(*node)){
        hot = node->parent;
        FromParentTo(*node) = node->lc;
        deleteNodeSucc = node->lc;
        delete node;
        return deleteNodeSucc;
    }

    if(!HasLChild(*node) && HasRChild(*node)){
        hot = node->parent;
        FromParentTo(*node) = node->rc;
        deleteNodeSucc = node->rc;
        delete node;
        return deleteNodeSucc;
    }


    /**
     * 双分支的情况,
     * 1 寻找 这个要删除节点的后继节点
     * 2 交换两个节点的数据
     * 3 hot = succ -> parent 删除后继节点
     * 后继节点也可能存在子节点
     */
    if(HasLChild(*node) && HasRChild(*node)){
        BinNodePosi(T) succ = node->succ();
        myswap(succ->data, node->data);
        hot = succ->parent;
        FromParentTo(*succ) = succ->rc;
        deleteNodeSucc = succ->rc;
        delete succ;

        return deleteNodeSucc;
    }

}


template <typename T>
bool BST<T>::remove(const T&e){// 删除
    BinNodePosi(T) node = search(e);
    // 并未找到
    if(node == NULL){
        return false;
    }

    removeAt(node, _hot);
    this->_size --;
    this->updateHeightAbove(_hot);
    return true;
}


#endif //CPP_LEARNING_BST_HPP
